package 每日一题OJ;

import java.util.ArrayList;
import java.util.List;

/**
 * @author shy_black
 * @date 2019/8/20 19:02
 * @Description:
 */
public class _46_全排列 {
    public List<List<Integer>> permute(int[] arr) {

        List<List<Integer>> res = new ArrayList<>();
        List<Integer> l = new ArrayList<>();

        fullList(arr, l, res);
        return res;
    }

    //使用回溯（递归）解答，每次向l中添加元素时，都先判断l中是否有该元素，如没有，才进行添加，
    //之后进入递归，递归出来将当前元素删除，去试排列
    public static void fullList(int[] arr, List<Integer> l, List<List<Integer>> res) {
        //如果l的大小已经等于arr的大小，说明此次排列完成，进入下次排列，在res中新增一个大小为l的空间
        if (l.size() == arr.length) {
            //把当前的排列复制一份放入res中，返回递归，去再次尝试，直到所有for执行完毕
            res.add(new ArrayList<Integer>(l));
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            if (l.contains(arr[i]))
                continue;
            l.add(arr[i]);
            fullList(arr, l, res);
            l.remove(l.size() - 1);
        }
    }

}